#define  _CRT_SECURE_NO_WARNINGS
class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        int n = nums.size(), ret = 1;
        vector<int> dp(n, 1);
        for (int i = 1; i < n; i++)
            for (int j = i; j >= 0; j--)
                if (nums[i] > nums[j])
                    ret = max(ret, dp[i] = max(dp[i], dp[j] + 1));
        return ret;
    }
};